//
// Created by wenyaxi on 24-10-29.
//
#include <common.h>

class Solution {
public:
    unordered_map<TreeNode *, TreeNode *> relationship_map;
    unordered_set<TreeNode *> path_p;
    unordered_set<TreeNode *> path_q;

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        relationship_map[root] = nullptr;
        init_relation(root);
        for(;;) {
            if(path_q.contains(p)) {
                return p;
            }
            if(path_p.contains(q)) {
                return q;
            }
            path_p.insert(p);
            path_q.insert(q);
            p=relationship_map[p];
            q=relationship_map[q];
            path_p.insert(p);
            path_q.insert(q);
        }
    }

    void init_relation(TreeNode *node) {
        if (node == nullptr) return;
        if(node->left) {
            relationship_map[node->left] = node;
            init_relation(node->left);
        }
        if(node->right) {
            relationship_map[node->right] = node;
            init_relation(node->right);
        }
    }
};

int main(int argc, char *argv[]) {
    auto *n0 = new TreeNode(0);
    auto *n1 = new TreeNode(1);
    auto *n2 = new TreeNode(2);
    auto *n3 = new TreeNode(3);
    auto *n4 = new TreeNode(4);
    auto *n5 = new TreeNode(5);
    auto *n6 = new TreeNode(6);
    auto *n7 = new TreeNode(7);
    auto *n8 = new TreeNode(8);
    auto *n9 = new TreeNode(9);
    auto *n10 = new TreeNode(10);
    n0->left = n1;
    n0->right = n2;
    n1->left = n3;
    n1->right = n4;
    n2->left = n5;
    n2->right = n6;
    n4->left=n7;
    n4->right = n8;
    n5->right = n9;
    n7->left=n10;
    Solution s;
    auto lowest_common_ancestor = s.lowestCommonAncestor(n0, n8, n10);
    cout<<lowest_common_ancestor->val;
}
